/* cdsl_dlist.c - simple doubly-linked list
 * Copyright (c) 2009 Charles Wilson
 * This file is part of the C Data Structures Library.
 *
 * Derived from code released into the public domain by Julienne Walker:
 *   http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_linklist.aspx
 *
 * mergesort code in cdsl_dlist_sort based on that from
 *   http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
 *   Copyright (c) 2001 Simon Tatham.
 *   and released under a license identical to that below.
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
*/
#include "cdsl_dlist.h"

#ifdef __cplusplus
#include <cstdlib>

using std::malloc;
using std::free;
using std::size_t;
#else
#include <stdlib.h>
#endif

struct cdsl_dlist_node
  {
    void              *data;
    cdsl_dlist_node_t *prev;
    cdsl_dlist_node_t *next;
  };

struct cdsl_dlist
  {
    cdsl_dlist_node_t *head;
    cdsl_dlist_node_t *tail;
    size_t             size;
  };


cdsl_dlist_node_t *cdsl_dlist_begin (cdsl_dlist_t *list)
  {
    if (list) return list->head->next;
    return NULL;
  }
cdsl_dlist_node_t *cdsl_dlist_end   (cdsl_dlist_t *list)
  {
    if (list) return list->tail;
    return NULL;
  }
cdsl_dlist_node_t *cdsl_dlist_next  (cdsl_dlist_node_t *node)
  {
    if (node) return node->next;
    return NULL;
  }
cdsl_dlist_node_t *cdsl_dlist_prev  (cdsl_dlist_node_t *node)
  {
    if (node) return node->prev;
    return NULL;
  }
cdsl_dlist_node_t *cdsl_dlist_rbegin(cdsl_dlist_t *list)
  {
    if (list) return list->tail->prev;
    return NULL;
  }
cdsl_dlist_node_t *cdsl_dlist_rend  (cdsl_dlist_t *list)
  {
    if (list) return list->head;
    return NULL;
  }
cdsl_dlist_node_t *cdsl_dlist_rnext (cdsl_dlist_node_t *node)
  {
    if (node) return node->prev;
    return NULL;
  }
cdsl_dlist_node_t *cdsl_dlist_rprev (cdsl_dlist_node_t *node)
  {
    if (node) return node->next;
    return NULL;
  }
void              *cdsl_dlist_value (cdsl_dlist_node_t *node)
{
  if (node) return node->data;
  return NULL;
}
size_t             cdsl_dlist_size  (cdsl_dlist_t *list)
{
  if (list) return list->size;
  return (size_t)0;
}


/*
  Create a new node with the given data and links
  Returns a pointer to the new node, or NULL on error
*/
cdsl_dlist_node_t *cdsl_dlist_new_node (void *data, cdsl_dlist_node_t *prev, cdsl_dlist_node_t *next)
  {
    cdsl_dlist_node_t *rv = malloc ( sizeof *rv );

    if (rv != NULL)
      {
        rv->data = data;
        rv->prev = prev;
        rv->next = next;
      }

    return rv;
  }

/*
  Create a new list and its head/tail sentinels
  Returns a pointer to the new list, or NULL on error
*/
cdsl_dlist_t *cdsl_dlist_new_list (void)
  {
    cdsl_dlist_t *rv = malloc ( sizeof *rv );

    /* create a block we can break out of */
    while (rv != NULL)
      {
        cdsl_dlist_node_t *tail = cdsl_dlist_new_node (NULL, NULL, NULL);
        if (tail == NULL)
          {
            /* Release the list if the sentinel couldn't be allocated */
            free ( rv );
            rv = NULL;
            break;
          }

        cdsl_dlist_node_t *head = cdsl_dlist_new_node (NULL, NULL, NULL);
        if (head == NULL)
          {
            /* Release the list if the sentinel couldn't be allocated */
            free (tail);
            tail = NULL;
            free (rv);
            rv = NULL;
            break;
          }

        /* Add the sentinels to the list */
        rv->tail = tail;
        rv->head = head;

        /* Link the tail to the head and vice-versa */
        rv->tail->prev = rv->head;
        rv->head->next = rv->tail;

        rv->size = 0;
        break;
      }

    return rv;
  }

/*
  Destroy a single given node, assuming it has been unlinked
  Optionally destroy the data contained in the node
  Returns the next node specified by the link
*/
cdsl_dlist_node_t *cdsl_dlist_destroy_node (cdsl_dlist_node_t *node, cdsl_dlist_rel_f destroy)
  {
    cdsl_dlist_node_t *rv = NULL;

    if (node != NULL)
      {
        /* Save a reference to the next node
           because we're about to destroy this one
        */
        rv = node->next;

        if (destroy != NULL)
          (*destroy) (node->data);

        free (node);
      }

    return rv;
  }

/*
  Destroy all nodes in a given list
  Optionally destroy all data in each node
*/
void cdsl_dlist_destroy_list (cdsl_dlist_t *list, cdsl_dlist_rel_f destroy)
{
  while (list->head != NULL)
    list->head = cdsl_dlist_destroy_node (list->head, destroy);
}

/*
  Insert a new node after the given node
  Returns a pointer to the new node or NULL on failure
  If pos is list->tail, append to end of list.
*/
cdsl_dlist_node_t *cdsl_dlist_insert_after (cdsl_dlist_t *list, cdsl_dlist_node_t *pos, void *data)
  {
    cdsl_dlist_node_t *rv = NULL;

    if (list != NULL && pos != NULL)
      {
        if (pos != list->tail)
          {
            /* Create a new node and set the next link */
            rv = cdsl_dlist_new_node (data, pos, pos->next);

            if (rv != NULL)
              {
                if (pos->next != NULL)
                  pos->next->prev = rv;

                pos->next = rv;
                ++list->size;
              }
          }
        else
          rv = cdsl_dlist_insert_before (list, pos, data);
      }

    return rv;
  }

/*
  Insert a new node before the given node
  Returns a pointer to the new node or NULL on failure
  If pos is list->head, insert at beginning of list.
*/
cdsl_dlist_node_t *cdsl_dlist_insert_before (cdsl_dlist_t *list, cdsl_dlist_node_t *pos, void *data)
  {
    cdsl_dlist_node_t *rv = NULL;

    if (list != NULL && pos != NULL)
      {
        if (pos != list->head)
          {
            /* Create a new node and set the next link */
            rv = cdsl_dlist_new_node (data, pos->prev, pos);

            if (rv != NULL)
              {
                if (pos->prev != NULL)
                  pos->prev->next = rv;

                pos->prev = rv;
                ++list->size;
              }
          }
        else
          rv = cdsl_dlist_insert_after (list, pos, data);
      }

    return rv;
  }

/*
  Remove the selected node
  Returns the removed node or NULL on failure
*/
cdsl_dlist_node_t *cdsl_dlist_remove_node (cdsl_dlist_t *list, cdsl_dlist_node_t *pos)
  {
    cdsl_dlist_node_t *rv = NULL;

    if (list != NULL && pos != NULL)
      {
        /* Shift off of the sentinels */
        if (pos == list->head)
          pos = pos->next;

        if (pos == list->tail)
          pos = pos->prev;

        if (pos != list->head)
          {
            /* Remove a non-sentinel node */
            rv = pos;

            /* Reset the list links if necessary */
            if (rv->prev != NULL)
              rv->prev->next = rv->next;

            if (rv->next != NULL)
              rv->next->prev = rv->prev;

            /* Clean up the old node */
            rv->prev = rv->next = NULL;
            --list->size;
          }
      }

    return rv;
  }

/*
  Insert a new node in sorted order
  Returns a pointer to the new node or NULL on failure
*/
cdsl_dlist_node_t *cdsl_dlist_insert_sorted (cdsl_dlist_t *list, void *data, cdsl_dlist_cmp_f compare)
  {
    cdsl_dlist_node_t *rv = NULL;

    if (list != NULL)
      {
        /* Find the sorted position of the new node */
        cdsl_dlist_node_t *it = list->head->next;
        while (it != list->tail && (*compare) (it->data, data) < 0)
          {
            it = it->next;
          }
        /* Delegate the insertion to an existing function */
        rv = cdsl_dlist_insert_before (list, it, data);
      }
    return rv;
  }

/* use mergesort algorithm -- most efficient for linked lists */
void cdsl_dlist_sort (cdsl_dlist_t *list, cdsl_dlist_cmp_f compare)
{
  cdsl_dlist_node_t *p, *q, *e, *tail, *head;
  int insize, nmerges, psize, qsize, i;

  if (list == NULL) return;                   /* null  */
  if (list->head->next == list->tail) return; /* empty */

  /* inside the loop below we sort the *contents* of the linked list,
   * not including the sentinels. Therefore, we must 'strip' the
   * sentinels. */
  head = list->head->next;       /* remove head sentinel */
  head->prev = NULL;
  tail = list->tail->prev;       /* remove tail sentinel */
  tail->next = NULL;

  insize = 1;
  while (1)
    {
      p = head;
      head = NULL;
      tail = NULL;

      nmerges = 0;  /* count number of merges we do in this pass */

      while (p)
        {
          nmerges++;  /* there exists a merge to be done */
          /* step `insize' places along from p */
          q = p;
          psize = 0;
          for (i = 0; i < insize; i++)
            {
              psize++;
              q = q->next;
              if (!q) break;
            }

          /* if q hasn't fallen off end, we have two heads to merge */
          qsize = insize;

          /* now we have two heads; merge them */
          while (psize > 0 || (qsize > 0 && q))
            {
              /* decide whether next element of merge comes from p or q */
              if (psize == 0)
                {
                  /* p is empty; e must come from q. */
                  e = q;
                  q = q->next;
                  qsize--;
                }
              else if (qsize == 0 || !q)
                {
                  /* q is empty; e must come from p. */
                  e = p;
                  p = p->next;
                  psize--;
                }
              else if ((*compare)(p->data,q->data) <= 0)
                {
                  /* First element of p is lower (or same);
                   * e must come from p. */
                  e = p;
                  p = p->next;
                  psize--;
                }
              else
                {
                  /* First element of q is lower; e must come from q. */
                  e = q;
                  q = q->next;
                  qsize--;
                }

              /* add the next element to the merged head */
              if (tail)
                {
                  tail->next = e;
                }
              else
                {
                  head = e;
                }
              e->prev = tail;
              tail = e;
            }

          /* now p has stepped `insize' places along, and q has too */
          p = q;
        }
      tail->next = NULL;

      /* If we have done only one merge, we're finished. */
      if (nmerges <= 1)   /* allow for nmerges==0, the empty head case */
        break;

      /* Otherwise repeat, merging heads twice the size */
      insize *= 2;
    }

  /* now, raattach the sentinels */
  list->head->next = head;
  head->prev = list->head;
  list->tail->prev = tail;
  tail->next = list->tail;
}

cdsl_dlist_node_t *cdsl_dlist_find  (cdsl_dlist_t *list, void *data, cdsl_dlist_cmp_f compare)
  {
    cdsl_dlist_node_t *rv = NULL;
    if (list != NULL)
      {
        for (rv = list->head->next; rv != list->tail; rv = rv->next)
          {
            int rc = (*compare)(data, rv->data);
            if (rc == 0)
              break;
          }
        /* so caller doesn't have to check both NULL and tail */
        if (rv == list->tail)
          rv = NULL;
      }
    return rv;
  }

